[Python] 任意の次元のlistをシャッフルしたい

[Python] 任意の次元のlistをシャッフルしたい

Clock Icon2024.07.12

はじめに

以前書いた記事で、二重リストをシャッフルするのが面倒すぎて1次元のリストに変換して扱いました。でもリストの次元を落とすとバグを生み出す恐怖に追われることになります。

https://dev.classmethod.jp/articles/try-secret-source-simulation/

そこで、任意の次元のリストをシャッフルするクラスを自前で作っていきます。

構想

関数内でリストの次元を落として処理、元の次元に戻すというようにやっていけばうまくいきそうです。

ちなみに、やろうとしていることをカバーしているライブラリはぱっと見なさそうでした。車輪の再発明は回避です。

コード

import random

class ShuffleList:
    def __init__(self, target: list):
        # init
        self._temp_list = []
        self._target = target

    def _unpack(self, _target):
        if isinstance(_target, int):
            # _targetがintなら仮リストに追加
            self._temp_list.append(_target)
            return

        for _elem in _target:
            # そうでなければ、_targetの各要素について再帰
            self._unpack(_elem)
            continue

    def _pack(self, _target):
        if isinstance(_target, int):
            # _targetがintなら仮リストからpop
            return self._temp_list.pop()

        _ret_list = list()
        for _elem in _target:
            # そうでなければ、_targetの各要素について再帰
            ret_list.append(self._pack(_elem))
            continue
        return _ret_list

    def shuffle(self):
        self._unpack(self._target)
        random.shuffle(self._temp_list)
        return self._pack(self._target)

ざっと書きました。ちゃんとやるならvalidateくらいしたいですね。

テストしてみると、

# test 1
gave: [4719, 3584, 8817, 2025, 7029, 6098, 3316, 5953, 8539, 1648]
got : [1648, 8817, 3584, 5953, 6098, 3316, 2025, 8539, 4719, 7029]

# test 2
gave: [1, 2, 3, [4, 5, 6, [7, 8, 9, [10, 11, 12], [13, 14, 15], [16, 17, 18]]]]
got : [10, 3, 2, [13, 7, 4, [16, 18, 15, [5, 14, 6], [11, 12, 9], [17, 8, 1]]]]

という感じで、次元を保ったままシャッフルできました。任意の次元なので必ずしも正方である必要などはありません。ネストも好きにやっちゃって大丈夫です。

速度

要素数1000x1000の二次元listに対してのこのシャッフルと、要素数1000000のlistに対してのrandom.shuffleの実行結果を比較すると、

My Shuffle
0.26448855400085447 [s]
random.shuffle
0.20115196704864502 [s]

ぼちぼちですね。random.shuffleを処理に内包しているので少なくともそれ以上かかるのは仕方ないかなと思います。

10000x10000までのグラフを出してみました。

スクリーンショット 2024-07-12 13.56.20

まあ、ギリギリ許容範囲かなという気がします。大きくなるほど差が大きくなりますが、比でいうと差は縮んでいると言えます。(N=100のときの差:48%, N=9000のときの差:17%)

終わりに

今回は任意の次元のListをシャッフルするクラスを作りました。関数オブジェクトをオプションで渡せばsortとかもこのまま使えそうです。(多次元配列のソートにどれだけ意味があるかは知らんけど)

Share this article

facebook logohatena logotwitter logo

© Classmethod, Inc. All rights reserved.